#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
using namespace std;
typedef struct 
{
    int num;
    int x, y;
}maptype;

maptype tu[3000];
int w, h, n;
int tottime;
int ans;
int point;

bool comp(maptype t1, maptype t2)
{
    return t1.num > t2.num;
}    

int countneed(int x, int y)
{
    if (x==0 && y==0)
    {
        return (1+tu[point].y*2);
    }    
    else
    {
        return abs(tu[point].x-x)+abs(tu[point].y-y)+1+tu[point].y;
    }    
}    
int counttime(int x, int y)
{
    if (x==0 && y==0)      return tu[point].y+1;
    else return abs(tu[point].x-x)+abs(tu[point].y-y)+1;
}    

int main()
{
    int ncase, i, j;
    scanf("%d", &ncase);
    while (ncase-->0)
    {
        memset(tu, 0, sizeof(tu));
        n = 0;
        ans = 0;
        scanf("%d%d%d", &h, &w, &tottime);
        for (i=1; i<=h; ++i)
                for (j=1; j<=w; ++j)
                {
                    scanf("%d", &tu[++n].num);
                    tu[n].x = j;
                    tu[n].y = i;
                }    
        sort(tu+1, tu+n+1, comp); 
   /*     for (i=1; i<=n; ++i)
        printf("%d %d %d\n", tu[i].num, tu[i].x, tu[i].y); */
        int need, nowtime, nowx=0, nowy=0;
        nowtime = 0;
        point = 1;
        need = countneed(nowx, nowy);
        while (need+nowtime <= tottime)
        {
            ans += tu[point].num;
            if (tu[point].num == 0) break;
            nowtime += counttime(nowx, nowy);
            
            nowx = tu[point].x;
            nowy = tu[point].y;
            point++;            
            need = countneed(nowx, nowy);
        }
        printf("%d\n", ans);    
        
        
    }    
        
    
    

}    
